package Demo2_26;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-26
 * Time:20:58
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
                          //解法一：


// 定义解决方案类
//class Solution5 {
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if (root == null) {
//            return null;
//        }
//        if (root == p || root == q) {
//            return root;
//        }
//        TreeNode leftT = lowestCommonAncestor(root.left, p, q);
//        TreeNode rightT = lowestCommonAncestor(root.right, p, q);
//        if (leftT != null && rightT != null) {
//            return root;
//        } else if (leftT != null) {
//            return leftT;
//        } else if (rightT != null) {
//            return rightT;
//        }
//        return null;
//    }

                   //解法二：
                   class Solution5 {
                       public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
                           if(root==null){
                               return false;
                           }
                           stack.push(root);
                           if(root==node){
                               return true;
                           }
                           boolean flg=getPath(root.left,node,stack);
                           if(flg){
                               return true;
                           }
                           flg=getPath(root.right,node,stack);
                           if(flg){
                               return true;
                           }
                           stack.pop();
                           return false;
                       }
                       public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
                           if(root==null){
                               return null;
                           }
                           Stack<TreeNode> stack1=new Stack<>();
                           Stack<TreeNode> stack2=new Stack<>();
                           getPath(root,p,stack1);
                           getPath(root,q,stack2);
                           int size1=stack1.size();
                           int size2=stack2.size();
                           int size=size1-size2;
                           if(size<0){
                               size=Math.abs(size);
                               while(size!=0){
                                   stack2.pop();
                                   size--;
                               }
                           }
                           else{
                               while(size!=0){
                                   stack1.pop();
                                   size--;
                               }
                           }
                           while(!stack1.isEmpty()&&!stack2.isEmpty()){
                               if(stack1.peek()==stack2.peek()){
                                   return stack1.pop();
                               }else{
                                   stack1.pop();
                                   stack2.pop();
                               }
                           }
                           return null;
                       }

// 主类，用于测试
    public static void main(String[] args) {
        // 构建一个简单的二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        // 定义要查找的两个节点
        TreeNode p = root.left; // 节点 5
        TreeNode q = root.right; // 节点 1

        // 创建解决方案对象
        Solution5 solution = new Solution5();

        // 调用 lowestCommonAncestor 方法查找最近公共祖先
        TreeNode lca = solution.lowestCommonAncestor(root, p, q);

        // 输出结果
        if (lca != null) {
            System.out.println("最近公共祖先是: " + lca.val);
        } else {
            System.out.println("未找到最近公共祖先。");
        }
    }
}
